#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    using pii = pair<int, int>;
    int m = 0;
    int n = 0;
    void bfs(vector<vector<char>>& grid, int i, int j)
    {
        queue<pii> q;
        q.push(make_pair(i, j));
        grid[i][j] = 0;
        while (!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int i = 0;i < 4;++i)
            {

                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == '1')
                {
                    grid[a][b] = 0;
                    q.push(make_pair(a, b));
                }
            }
        }
    }
    int numIslands(vector<vector<char>>& grid)
    {
        m = grid.size(), n = grid[0].size();
        int res = 0;
        for (int i = 0;i < m;++i)
        {
            for (int j = 0;j < n;++j)
            {
                if (grid[i][j] == '1')
                {
                    ++res;
                    bfs(grid, i, j);
                }
            }
        }
        return res;
    }
};